// 堆可以看成一个完全二叉树
// 一个完全二叉树i节点的左孩子节点为2*i+1右孩子节点为2*i+2父节点为i-1/2取整，size是节点的个数
// 堆有两种大根堆和小根堆，其中大根堆为每一个节点的子树中他的根节点为最大值
const heapInsert = (arr: Array<number>,index:number) => {
    while (arr[index]>arr[(index-1)/2]){
        swap(arr,index,(index-1)/2)
        index= (index-1)/2
    }
}
const heapify = (arr: Array<number>,index:number,heapSize:number) => {
    let left = index * 2 + 1
    while(left < heapSize){
        let largest = left + 1 < heapSize && arr[left+1] > arr[left] ? left + 1 : left
        largest = arr[largest] > arr[index] ? largest : index
        if(largest == index) break
        swap(arr,largest,index)
        index = largest
        left = index * 2 + 1
    }
}
const swap = function (arr:number[],i: number,j: number){
    arr[i] = arr[i] ^ arr[j]
    arr[j] = arr[i] ^ arr[j]
    arr[i] = arr[i] ^ arr[j]
}
let arr = [4,31,5,21,4,6,2]
for(let i = 0; i < arr.length; i++){
    heapInsert(arr,i)
}
console.log(arr)
export {
    heapInsert, 
    heapify, 
    swap
}